package com.algorithm.base.greedy;

import org.springframework.stereotype.Service;

/**
 * 55. 跳跃游戏
 *
 * @author Amadeus
 * @date 2023/11/20
 */
@Service
public class CanJump {

    /**
     * 0为支点往前遍历
     *
     * @param nums nums
     * @return boolean
     */
    public boolean canJump(int[] nums) {
        if (nums[0] == 0 && nums.length > 1) {
            return false;
        }
        boolean result = true;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[j] > i - j) {
                        result = true;
                        break;
                    }
                    result = false;
                }
                if (!result) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 覆盖范围
     *
     * @param nums nums
     * @return boolean
     */
    public boolean canJump2(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(nums[i] + i, cover);
            if (nums.length - 1 <= cover) {
                return true;
            }
        }
        return false;
    }

}
